/*
Source : https://leetcode.com/problems/set-matrix-zeroes/
Author : nflush@outlook.com
Date   : 2016-06-27
*/

/*
201. Bitwise AND of Numbers Range
Total Accepted: 36921 Total Submissions: 118310 Difficulty: Medium

Given a range [m, n] where 0 <= m <= n <= 2147483647, return the bitwise AND of all numbers in this range, inclusive.

For example, given the range [5, 7], you should return 4.

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

Subscribe to see which companies asked this question
*/

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        if (m==n) return m;
        unsigned int base = m & n;
        unsigned int diff = n - m;
        if (base <= diff) return 0;
        for(int i = 1; i< diff;i<<=1){
            base &= ~i;
        }
        return base;
    }
};

class Solution {
public:
    int rangeBitwiseAnd(int m, int n) {
        if (m==n) return m;
        unsigned int base = m & n;
        unsigned int diff = n - m;
        if (base <= diff) return 0;
        while (base & (base-1)){
            if ((base ^ (base-1)) < diff){
                base = base & (base-1);
            } else {
                break;
            }
        }
        return base;
    }
};

